//
// Description: 雪球的书架
// Created by Loading on 2021/3/28.
//

// 雪球是一个爱读书的小朋友，它有一个长长的书架，所有的书排成一行。一天，他发现自己书架上的书太多了，而且排列混乱，他希望把书整理一下。
// 整理的目标是把所有颜色相同的书都摆放在一起，整理的方法是每次任意选择一本书抽出来放到书架的最右侧。
// 那么雪球要完成书架的整理，需要的最少操作次数是多少呢？

// Input
// 第一行整数n (1<=n<=5*10^5) ，表示书的总数
// 第二行是n个整数a1 … an(1<=ai<=n)，表示每本书的颜色，颜色用整数表示
//
// Output
// 完成书架整理需要的最少操作次数

// Examples
//
// Input
// 6
// 2 1 1 2 2 3
//
// Output
// 2

// Input
// 5
// 1 2 2 1 1
//
// Output
// 1

// 动态规划
// 每本书都移动，一定可以达成目标，需要n次移动
// 可以暂定某一种颜色的不动，仍然可以达成目标
// 也可以暂定某几种颜色的不动，但是这几种颜色的书的位置不能相交，分别在独立的区间，求哪几个不需要移动的独立区间的书的数量和最大，则操作次数就越少

#include <bits/stdc++.h>

using namespace std;

#define N 500050

int main() {
    vector<int> l(N);           //每个元素第一次出现的下标
    vector<int> r(N);           //每个元素最后一次出现的下标
    vector<int> cnt(N);         //元素总次数
    vector<int> max_not_op(N);  //下标i 及其后边，不需要移动的书的数量

    int n;
    cin >> n;

    for (auto &x : l) {
        x = INT_MAX;
    }
    vector<int> vec(n);
    for (int i = 0; i < n; ++i) {
        cin >> vec[i];
        l[vec[i]] = min(l[vec[i]], i);
        r[vec[i]] = max(r[vec[i]], i);
    }

    cnt[vec[n - 1]]++;
    max_not_op[n - 1] = 1;
    for (int i = n - 2; i >= 0; --i) {
        cnt[vec[i]]++;
        //假设当前位置移动，则不需要移动的数量等于其后一个下标值
        max_not_op[i] = max_not_op[i + 1];

        //假设当前位置不动，计算当前位置移动和不动时哪个状态下不需要移动的书的数量更多，更新值
        if (i == l[vec[i]]) {
            //找到元素第一次出现的位置
            //假设当前位置不动时，不需要移动的书的总数量为：
            //当前元素出现的总次数 + 当前元素最后一次出现的下标的后一个位置的不需要移动的书的数量（区间合并）
            max_not_op[i] = max(max_not_op[i], cnt[vec[i]] + max_not_op[r[vec[i]] + 1]);
        } else {
            //还未找到元素第一次出现的位置
            //假设当前位置不动时，如果元素总次数大于当前值，则本元素皆可不动，更新值
            max_not_op[i] = max(max_not_op[i], cnt[vec[i]]);
        }
    }

    cout << n - max_not_op[0] << endl;
}